package com.datastructure.test.judgeissubsequence;

public class JudgeIsSubSequence {

    public static void main(String[] args) {
        JudgeIsSubSequence judgeIsSubSequence = new JudgeIsSubSequence();
        boolean subsequence = judgeIsSubSequence.isSubsequence("nowef", "nowcoder");
        System.out.println(subsequence);
    }

    public boolean isSubsequence (String S, String T) {
        // write code here
        int rows = S.length();
        int list = T.length();
        int[][] res = new int[rows+1][list+1];
        for (int i = 1; i < res.length; i++) {
            for (int j = 1; j < res[0].length; j++) {
                if(S.charAt(i-1)==T.charAt(j-1)){
                    res[i][j]=res[i-1][j-1]+1;
                }else {
                    res[i][j]=Math.max(res[i-1][j],res[i][j-1]);
                }
                if(res[i][j] >= rows){
                    return true;
                }
            }
        }
        return res[rows][list] >= rows;
    }
}
